import com.sun.javaws.IconUtil;

import java.util.Arrays;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-10-18
 * Time:20:22
 */
public class UnionFindSet {
    public int[] elem;

    public UnionFindSet(int n) {
        this.elem = new int[n];
        Arrays.fill(elem, -1);
    }

    /**
     * 查找数据 x 的根节点
     * @param x
     * @return 下标
     */
    public int findRoot(int x) {
        if (x < 0) {
            throw new IndexOutOfBoundsException("下标不合法，是负数！");
        }
        while (elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }


    /**
     * 查询 x1 和 x2 是不是同一个集合
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameUnionFindSet(int x1, int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if (index1 == index2) {
            return true;
        }
        return false;
    }

    /**
     * 合并操作
     * @param x1
     * @param x2
     */
    public void union(int x1, int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if (index1 == index2) {
            return;
        }
        elem[index1] += elem[index2];
        elem[index2] = index1;
    }

    public int getCount() {
        int count = 0;
        for (int x : elem) {
            if (x < 0) {
                count++;
            }
        }
        return count;
    }

    public void print() {
        for (int x : elem) {
            System.out.println(x + " ");
        }
        System.out.println();
    }

    //省份的数量
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFindSet ufs = new UnionFindSet(n);
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[i].length; j++) {
                if (isConnected[i][j] == 1) {
                    ufs.union(i, j);
                }
            }
        }
        return ufs.getCount();
    }

    //等式的满足性
    public boolean equationsPossible(String[] equations) {
        UnionFindSet ufs = new UnionFindSet(26);
        for (int i = 0; i < equations.length; i++) {
            if (equations[i].charAt(1) == '=') {
                ufs.union(equations[i].charAt(0)-'a',equations[i].charAt(3)-'a');
            }
        }
        for (int i = 0; i < equations.length; i++) {
            if (equations[i].charAt(1) != '=') {
                boolean flg = ufs.isSameUnionFindSet(equations[i].charAt(0)-'a',equations[i].charAt(3)-'a');
                if (flg == true) {
                    return false;
                }
            }
        }
        return true;
    }
}
